//给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。
//
// 非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
//
//
//
// 示例 1：
//
//
//
//
//输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
//输出：13
//解释：
//所有非零偏移下降路径包括：
//[1,5,9], [1,5,7], [1,6,7], [1,6,8],
//[2,4,8], [2,4,9], [2,6,7], [2,6,8],
//[3,4,8], [3,4,9], [3,5,7], [3,5,9]
//下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
//
//
// 示例 2：
//
//
//输入：grid = [[7]]
//输出：7
//
//
//
//
// 提示：
//
//
// n == grid.length == grid[i].length
// 1 <= n <= 200
// -99 <= grid[i][j] <= 99
//
//
// Related Topics 数组 动态规划 矩阵 👍 190 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//java:下降路径最小和  II
public class Q1289MinimumFallingPathSumIi {
    public static void main(String[] args){
        Solution solution = new Q1289MinimumFallingPathSumIi().new Solution();
        solution.minFallingPathSum((new int[][]{{1,2,3},{4,5,6},{7,8,9}}));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minFallingPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        System.arraycopy(grid[0], 0, dp[0], 0, n);
//        for (int i = 1; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                int val = Integer.MAX_VALUE;
//                for (int k = 0; k < n; k++) {
//                    if (k != j) {
//                        val = Math.min(val, dp[i - 1][k]);
//                    }
//                }
//                // 找到不是p的位置
//                dp[i][j] = grid[i][j] + val;
//            }
//        }
        // 通过保存多层的最小值和次最小值，实现O(n^2)的复杂度
        // 初始化最小值和次最小值
        int minIndex1 = -1, minIndex2 = -1;
        for (int j = 0; j < n; j++) {
            if (grid[0][j] < ((minIndex1 == -1) ? Integer.MAX_VALUE : grid[0][minIndex1])) {
                minIndex2 = minIndex1;
                minIndex1 = j;
            } else if (grid[0][j] < ((minIndex2 == -1) ? Integer.MAX_VALUE : grid[0][minIndex2])) {
                minIndex2 = j;
            }
        }

        for (int i = 1; i < m; i++) {
            // 保存当前这层的最小值和次最小值
            int minIndex11 = -1, minIndex12 = -1;
            for (int j = 0; j < n; j++) {
                if (j != minIndex1) {
                    dp[i][j] = grid[i][j] + dp[i - 1][minIndex1];
                } else {
                    dp[i][j] = grid[i][j] + dp[i - 1][minIndex2];
                }

                if (dp[i][j] < ((minIndex11 == -1) ? Integer.MAX_VALUE : grid[0][minIndex11])) {
                    minIndex12 = minIndex11;
                    minIndex11 = j;
                } else if (dp[i][j] < ((minIndex12 == -1) ? Integer.MAX_VALUE : grid[0][minIndex12])) {
                    minIndex12 = j;
                }
            }
        }

        return Arrays.stream(dp[n - 1]).min().orElse(-1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}